package com.hanxiaozhang.greedy;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * 〈一句话功能简述〉<br>
 * 〈最大利润〉
 *
 * @author hanxinghua
 * @create 2021/9/23
 * @since 1.0.0
 */
public class MaxProfit {

    /**
     * 输入: 正数数组costs、正数数组profits、正数K、正数M。costs[i] 表示 i 号项目的花费。
     *  profits[i]表示 i 号项目在扣除花费之后还能挣到的钱(利润)。
     *  K表示你只能串行的最多做 k 个项目。M表示你初始的资金。
     * 说明: 每做完一个项目，马上获得的收益，可以支持你去做下一个项目。不能并行的做项目。
     * 输出：你最后获得的最大钱数。
     *
     * @param args
     */
    public static void main(String[] args) {

        int[] profits = {3, 4, 7, 8, 10, 333};
        int[] capital = {1, 2, 3, 4, 3, 22};
        System.out.println(maxProfit(2, 4, profits, capital));

    }

    public static int maxProfit(int K, int W, int[] profits, int[] capital) {
        // 小根堆队列
        PriorityQueue<Project> minCostQ = new PriorityQueue<>(new MinCostComparator());
        // 大根堆队列
        PriorityQueue<Project> maxProfitQ = new PriorityQueue<>(new MaxProfitComparator());
        for (int i = 0; i < profits.length; i++) {
            minCostQ.add(new Project(profits[i], capital[i]));
        }
        for (int i = 0; i < K; i++) {
            while (!minCostQ.isEmpty() && minCostQ.peek().c <= W) {
                maxProfitQ.add(minCostQ.poll());
            }
            // 没有项目可以做，直接返回
            if (maxProfitQ.isEmpty()) {
                return W;
            }
            W += maxProfitQ.poll().p;
        }
        return W;
    }

    /**
     * 项目实体
     */
    public static class Project {
        public int p;
        public int c;

        public Project(int p, int c) {
            this.p = p;
            this.c = c;
        }
    }

    public static class MinCostComparator implements Comparator<Project> {

        @Override
        public int compare(Project o1, Project o2) {
            return o1.c - o2.c;
        }

    }

    public static class MaxProfitComparator implements Comparator<Project> {

        @Override
        public int compare(Project o1, Project o2) {
            return o2.p - o1.p;
        }

    }

}
